package cn.bellychang.leetcode.question207;

import java.util.*;

/**
 * @author ChangLiang
 * @date 2021/3/18
 */
public class Solution2 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        Map<Integer, ArrayList<Integer>> adj = new HashMap<>(numCourses);

        int[] inDegree = new int[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {

            if (!adj.containsKey(prerequisites[i][0])) {
                adj.put(prerequisites[i][0], new ArrayList<>());
            }
            adj.get(prerequisites[i][0]).add(prerequisites[i][1]);
            inDegree[prerequisites[i][1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        int count = 0;

        while (!queue.isEmpty()) {

            Integer temp = queue.remove();
            count++;
            if (!adj.containsKey(temp)) {
                continue;
            }

            ArrayList<Integer> arrayList = adj.get(temp);
            for (int i = 0; i < arrayList.size(); i++) {
                Integer index = arrayList.get(i);
                inDegree[index]--;
                if (inDegree[index] == 0) {
                    queue.add(index);
                }
            }
        }

        return count == numCourses;
    }
}
